package huawei.prefix;

/**
 * https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
 * 前缀和+ map+ 位运算
 */
public class J1248 {
    public static void main(String[] args){
        System.out.println(numberOfSubarrays(new int[]{1,1,2,1,1},3));
    }
    public static int numberOfSubarrays(int[] nums, int k) {
        int[] map = new int[nums.length+1];
        int preSum=0;
        int count =0;
        // pre[j]-pre[i]=k 则表示存在一个符合条件的子序列
        // 对于每个pre[j] 存在的数量=pre[j]-k=pre[i]的数量
        //特殊情况 pre[j]==k,是符合条件的,所以需要添加一个特殊的值pre[0]=1;
        map[0]=1;
        for (int num : nums) {
            preSum += (num&1);
            if (preSum >= k) {
                count += map[preSum - k];
            }
            map[preSum]++;
        }
        return count;
    }
}
